package com.lordjoe.sudoku;

import java.util.*;

/**
 * com.lordjoe.sudoku.SudokuCell
 * represents a cell in a sudoku board
 * with a possible specified value (set at start)
 * value (determined later)
 * set of constraints on row, column and box
 * also phi a set of current priors
 * User: Steve
 * Date: 4/7/12
 */
public class SudokuCell {
    public static final SudokuCell[] EMPTY_ARRAY = {};

    private Integer m_SpecifiedValue;
    private Integer m_Value;   // value determined
    private int m_MaxIndex; // index of highest probability
    private final SudokuBoard m_Board;
    private final int m_Col;
    private final int m_Row;
    // constraints on the cell
    private final SudokuConstraint[] m_Constraints = new SudokuConstraint[SudokuBoard.NUMBER_CONSTRAINT_TYPES];
    // constraints on the cell
    private int m_ConstraintMessageIndex;
    private final ConstraintMessage[] m_ConstraintMessages = new ConstraintMessage[SudokuBoard.NUMBER_CONSTRAINT_TYPES];
    // probabilities of each value (0 = 1 , 1 = 2 ...)
    private final double[] phi = new double[SudokuBoard.getBoardSize()];
    private final double[] last_phi = new double[SudokuBoard.getBoardSize()];

    public SudokuCell(final int pCol, final int pRow, SudokuBoard board) {
        m_Col = pCol;
        m_Row = pRow;
        m_Board = board;
    }

    public SudokuBoard getBoard() {
        return m_Board;
    }

    /*******************************************************
     *  This section is bookkeeping                        *
     *******************************************************/

    /**
     * stop on interesting cases - for debugging
     */
    private void breakIfInteresting()
    {
        int row = getRow() + 1;
        int col = getCol() + 1;
        if(row == 1 && col == 3)
            SudokuBoard.breakHere();
    }
    /**
     * this happend when we specify values in cells
     *
     * @param val
     */
    public void setSpecifiedValue(int val) {
        m_SpecifiedValue = val;
        int index = val - 1;
        for (int i = 0; i < phi.length; i++) {
            if (i == index)
                phi[i] = 1;
            else
                phi[i] = 0;

        }
    }

    public String toString() {
        String name = getRowColName();
        if (getValue() != null)
            name += "(" + getValue() + ")";
        return name;
    }

    public String getRowColName() {
        return " " + (m_Col + 1) + "," + (m_Row + 1);
    }


    public double[] getPhi() {
        return phi;
    }

    public boolean isSpecifiedX() {
        return m_SpecifiedValue != null;
    }

    private Integer getSpecifiedValue() {
        return m_SpecifiedValue;
    }

    public Integer getValue() {
        Integer ret = getSpecifiedValue();
        if (ret != null)
            return ret;
        return m_Value;
    }

    /**
     * set a specific value for a cell
     *
     * @param pValue
     */
    public void setValue(final Integer pValue) {
        // debugging stuff
        breakIfInteresting();
        if (m_SpecifiedValue != null)
            throw new IllegalStateException("cannot set a value when one specified");
        if (m_Value != null && m_Value != pValue)
            throw new IllegalStateException("cannot set a value when one specified");
        m_Value = pValue;
        // reset phi to
        Arrays.fill(phi,0);
        phi[pValue - 1] = 1;
        // say at least one cell is set
        getBoard().setValueSetThisIteration(true);
        if(SudokuBoard.SHOW_INTERMEDIATE_VALUES)  {
            System.out.print(" Setting " + this);
             showConstraints();
         }
      }

    private void showConstraints() {
        for (int i = 0; i < SudokuBoard.getBoardSize(); i++) {
            System.out.print(Integer.toString(i + 1));
            for (ConstraintMessage msg : m_ConstraintMessages)  {
                 if(msg != null && msg.valueBlocked(i)) {
                    System.out.print(msg.getTypeString());
                 }
            }
            System.out.print(" |");

        }
        System.out.println();
    }

    public boolean hasValue() {
        return getValue() != null;
    }

    public int getCol() {
        return m_Col;
    }

    public int getRow() {
        return m_Row;
    }

    public ConstraintMessage[] getConstraintMessages() {
        return m_ConstraintMessages;
    }

    public void addConstraint(SudokuConstraint constr) {
        int cIndex = constr.getType().getIndex();
        m_Constraints[cIndex] = constr;
    }


    /**
     * reset for a new round of messaging
     */
    public void resetMessaging() {
    //  Arrays.fill(m_ConstraintMessages, null);
        m_ConstraintMessageIndex = 0;
    }

    public void addConstraintMessage(ConstraintMessage cm) {
        m_ConstraintMessages[m_ConstraintMessageIndex++] = cm;
    }

    /**
     * remove values specified through constraints to speed convergence
     */
    public void initializePhi() {
        if (isSpecifiedX())
            return; // we already know
        Arrays.fill(phi, 1);  // all values = 1
        for (int i = 0; i < m_Constraints.length; i++) {
            SudokuConstraint constraint = m_Constraints[i];
            constraint.removeDeterminedStates(phi);
        }
        normalizePhi();
    }

    /**
     * make the sum of all probabilities equal 1
     */
    public void normalizePhi() {
    //    breakIfInteresting();
        double sum = 0;
        double maxValue = Double.MIN_VALUE;
        int maxIndex = 0;
        int numberNonZero = 0;
        for (int i = 0; i < phi.length; i++) {
             if (phi[i] > 0)   {
                 numberNonZero++;
                sum += phi[i] ;
                if(phi[i] > maxValue)  {
                    // do not let probability sink < i /size squared
                    maxValue =  phi[i] ;
                    maxIndex = i;
                }
             }
        }
        if(sum == 0)
            throw new IllegalStateException("0 probability all states in cell " + this);
        for (int i = 0; i < phi.length; i++) {
             phi[i] /= sum;
         }
        setMaxIndex(maxIndex);  // remember location of max
         if(numberNonZero == 1)
             setValue(maxIndex + 1);
     }


    public static final double MIN_PROBABILITY_IF_NOT_ZERO = 0.0; //1.0 / 81;


    /**
     * make the sum of all probabilities equal 1
     */
    public void normalizePhiX() {
    //    breakIfInteresting();
        double sum = 0;
        double maxValue = Double.MIN_VALUE;
        int maxIndex = 0;
        int numberNonZero = 0;
        for (int i = 0; i < phi.length; i++) {
             if (phi[i] > 0)   {
                 numberNonZero++;
                sum += Math.max(phi[i],MIN_PROBABILITY_IF_NOT_ZERO);
                if(phi[i] > maxValue)  {
                    // do not let probability sink < i /size squared
                    maxValue =  phi[i] ;
                    maxIndex = i;
                }
             }
        }
        if(sum == 0)
            throw new IllegalStateException("0 probability all states in cell " + this);
        for (int i = 0; i < phi.length; i++) {
            double v = phi[i];
            if(v > 0)     {
                phi[i] =  Math.max(v,MIN_PROBABILITY_IF_NOT_ZERO) /  sum;
                if (numberNonZero == 1  )
                    setValue((Integer) i + 1); // we are 1 based

            }
        }
        setMaxIndex(maxIndex);
     }

    public int getMaxIndex() {
        return m_MaxIndex;
    }

    public double getMaxProbability() {
        return phi[getMaxIndex()];
    }

    public void setMaxIndex(final int pMaxIndex) {
        m_MaxIndex = pMaxIndex;
    }

    public int getConstraintMessageIndex() {
        return m_ConstraintMessageIndex;
    }

    public void setConstraintMessageIndex(final int pConstraintMessageIndex) {
        m_ConstraintMessageIndex = pConstraintMessageIndex;
    }
    /*******************************************************
     *  This section is the algorithm                        *
     *******************************************************/

    /**
     * determine the probabilities to sent so a constraint  this
     * is called bu the message constructor
     * @param cm !null cell message
     * @param cnstr !null target constraint
     */
    public void populateCellMessage(CellMessage cm, SudokuConstraint cnstr)
    {
        double[] m_Values = cm.getValues();
        // value is assigned
        if( hasValue()) {
            m_Values[ getValue() - 1] = 1;
            return;
        }
        ConstraintMessage[] msgs = getConstraintMessages();
        Arrays.fill(m_Values,1);
        for (ConstraintMessage msg : msgs) {
            if (msg == null) {
                System.arraycopy( getPhi(), 0, m_Values, 0, SudokuBoard.getBoardSize());
                return;
            }
            if (msg.getConstraint() == cnstr) {
                continue;
            }
            double[] values = msg.getValues();
            for (int i = 0; i < values.length; i++) {
                m_Values[i] *= values[i];

            }
        }
        cm.normalize();

    }

    public static final int FRACTION_ORIGINAL_PROBABILITY_TO_RETAIN = 1;
    /**
     * reset probabilities after messaging fro next round
     * This is a critical step of the algorithm
     */
    public void resetStateAfterMessaging() {
        // debugging stuff
       // breakIfInteresting();

        Integer value = getValue();
        if (value != null)
            return; // already have a value
        // start with all 1s
        double[] messageProbabilities = new double[SudokuBoard.getBoardSize()];
        Arrays.fill(messageProbabilities, 1);
        for (ConstraintMessage cm : m_ConstraintMessages) {
            double[] values = cm.getValues();
            for (int i = 0; i < values.length; i++) {
                double v = values[i];
                messageProbabilities[i] *= v;
            }
        }
        // make a copy of phi before we update
        System.arraycopy(last_phi,0,phi,0,last_phi.length);
        // is this right
        for (int i = 0; i < messageProbabilities.length; i++) {
            if(messageProbabilities[i] == 0)
                  phi[i] = 0;
            else    // add some inertia
                 phi[i] = (FRACTION_ORIGINAL_PROBABILITY_TO_RETAIN * phi[i] + messageProbabilities[i]) / (FRACTION_ORIGINAL_PROBABILITY_TO_RETAIN + 1);
        }

         normalizePhi();

    }

    public void messageConstraints() {
        for (SudokuConstraint constraint : m_Constraints) {
            CellMessage msg = new CellMessage(this, constraint);
            constraint.addCellMessage(msg);
        }
    }

    // if the next probability is too close to this do not guess
    public static final double MAX_FRACTION_TOO_CLOSE = 0.4;

    public void maybeSetValue() {
        int maxIndex = getMaxIndex();
        double test = phi[maxIndex] * MAX_FRACTION_TOO_CLOSE;
        for (int i = 0; i < phi.length; i++) {
            if(i == maxIndex)
                continue;
            double v = phi[i];
            if(v == 0)
                continue;
            if(v > test) {
                unBalance();
                return;
            }
         }
        System.out.println("Guessing " + this + " is " + maxIndex + 1);
        setValue(maxIndex + 1);
    }

    /**
     * give more probability to max
     */
    public void unBalance() {
        int maxIndex = getMaxIndex();
         phi[maxIndex] *= 2;
        for (int i = 0; i < phi.length; i++) {
            if(i == maxIndex)
                continue;
            double v = phi[i];
            if(v == 0)
                continue;
            phi[i] /= 2;
         }
        normalizePhi();
    }
}
